/**
 * 给定字符串S和T，问按照顺序合并出来的字符串，其最长回文子串长度是多少
 * 令D[sa][sb][ta][tb]为S[sa...sb]和T[ta...tb]能够合出来的最长回文子串
 * 注意不是其内能够合出来的最长回文子串，如果是其内其实就是问的序列
 * 因此D的取值，用-1表示不是回文子串，用正数表示是回文且长度（其实长度就是sb-sa+1+ta-tb+1）。
 * 当某一方没有时，就是单独一个字符串的回文子串，也可以写成DP形式
 * 当范围都合法的话，只有两端的字符相等，才有可能，一共有4种情况
 * 这个代码极慢，刚好2s过。
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using vpii = vector<pii>;

void chkmax(int & d, int a){
    if(a < 0) return;
    if(d < 0 or d < a) d = a;
}

int chkadd(int a, int b){
    if(a < 0 or b < 0) return -1;
    return a + b;
}

int N, M;
string S, T;
vector<vector<vector<vi>>> D;
vector<vi> DS, DT;

int dp(int a, int b, const string & s, vector<vi> & d){
    if(-2 != d[a][b]) return d[a][b];
    if(a == b) return d[a][b] = 1;
    if(a > b) return d[a][b] = 0;

    auto & ans = d[a][b];
    ans = -1;
    if(s[a] == s[b]){
        chkmax(ans, chkadd(2, dp(a + 1, b - 1, s, d)));
    } 
    return ans;  
}

int dfs(int sa, int sb, int ta, int tb){
    if(-2 != D[sa][sb][ta][tb]) return D[sa][sb][ta][tb];
    if(sa > sb){
        return D[sa][sb][ta][tb] = dp(ta, tb, T, DT);
    }
    if(ta > tb){
        return D[sa][sb][ta][tb] = dp(sa, sb, S, DS);
    }

    auto & d = D[sa][sb][ta][tb];
    d = -1;
    if(sa != sb and S[sa] == S[sb]){
        chkmax(d, chkadd(2, dfs(sa + 1, sb - 1, ta, tb)));
    }
    if(ta != tb and T[ta] == T[tb]){
        chkmax(d, chkadd(2, dfs(sa, sb, ta + 1, tb - 1)));
    }
    if(S[sa] == T[tb]){
        chkmax(d, chkadd(2, dfs(sa + 1, sb, ta, tb - 1)));
    }
    if(S[sb] == T[ta]){
        chkmax(d, chkadd(2, dfs(sa, sb - 1, ta + 1, tb)));
    }
    // if(sa + 1 <= sb){
    //     chkmax(d, dfs(sa + 1, sb, ta, tb));
    //     chkmax(d, dfs(sa, sb - 1, ta, tb));
    // }
    // if(ta + 1 <= tb){
    //     chkmax(d, dfs(sa, sb, ta + 1, tb));
    //     chkmax(d, dfs(sa, sb, ta, tb - 1));        
    // }
    return d;
}

void work(){
    cin >> S >> T;
    N = S.length();
    M = T.length();
    S = " " + S;
    T = " " + T;

    DS.assign(N + 2, vi(N + 2, -2));
    DT.assign(M + 2, vi(M + 2, -2)); 
    D.assign(N + 2, vector<vector<vi>>(N + 2, vector<vi>(M + 2, vi(M + 2, -2))));
    int ans = -2;
    for(int i=1;i<=N;++i)for(int j=i;j<=N;++j)for(int u=1;u<=M;++u)for(int v=u;v<=M;++v){
        chkmax(ans, dfs(i, j, u, v));
    }

#ifndef ONLINE_JUDGE
    // for(int i=1;i<=N;++i)for(int j=i;j<=N;++j){
    //     cout << "(" << i << ", " << j << ") = " << dp(i, j, S, DS) << endl; 
    // }
    // for(int i=1;i<=M;++i)for(int j=i;j<=M;++j){
    //     cout << "(" << i << ", " << j << ") = " << dp(i, j, T, DT) << endl; 
    // }

    for(int i=1;i<=N;++i)for(int j=i;j<=N;++j)for(int u=1;u<=M;++u)for(int v=u;v<=M;++v){
        cout << "(" << i << ", " << j << ", " << u << ", " << v << ") = " << dfs(i, j, u, v) << endl;
    }
#endif

    cout << ans << "\n";
    return;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1;
    cin >> nofkase;
    while(nofkase--) work();
    return 0;
}